#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


ListNode *partition(ListNode *head, int x) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!head)
        return NULL;
    ListNode *pShead = new ListNode(0);
    ListNode *pGhead = new ListNode(0);
    ListNode *pS = pShead;
    ListNode *pG = pGhead;
    
    while(head){
        if(head->val < x){
            pS->next = head;
            pS = pS->next;
        }
        else{
            pG->next = head;
            pG = pG->next;
        }
        head = head->next;
    }

    pS->next = pGhead->next;
    pG->next = NULL;
    
    ListNode *pRes = pShead->next;
    delete pShead;
    delete pGhead;
    return pRes;
}


int main(){

    return 0;
}